package com.cn.algorithm01;

import java.util.Arrays;

/**
 * @author hels
 * @version 1.0
 * @date 2021/10/12 11:48
 */
public class Code04_HalfLeft {

    // 生成随机数组,保持有序
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int)((maxSize+1)*Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)((maxValue+1)*Math.random());
        }
        Arrays.sort(arr);
        return arr;
    }

    // 输出数组
    public static void printArray(int[] arr, int num) {
        for (int n : arr) {
            System.out.print(n + " ");
        }
        System.out.println("=随机数=" + num );
    }

    public static void main(String[] args) {
        int maxSize = 10, maxValue =30;
        int times = 100;
        boolean succeed = true;

        for (int i = 0; i < times; i++) {
            int num = (int)((maxValue+1)*Math.random());
            int[] arr = generateRandomArray(maxSize, maxValue);

            if (leftIndex(arr, num) != testLeft(arr, num)) {
                printArray(arr, num);
                System.out.println(num);
                System.out.println(leftIndex(arr, num));
                System.out.println("暴力方法：" + testLeft(arr, num));
                System.out.println("======");
                succeed = false;
            }
            printArray(arr, num);
            System.out.println(num);
            System.out.println(leftIndex(arr, num));
            System.out.println("暴力方法：" + testLeft(arr, num));
        }

        System.out.println(succeed ? "nice" : "fuck");

    }

    // 找出大于等于num最左边的下标
    public static int leftIndex(int[] arr, int num) {
        int index = -1;

        if (arr == null || arr.length == 0) {
            return index;
        }

        int L = 0, R = arr.length - 1;
        while (L <= R) {
            int mid = (L + R)/2;
            if (arr[mid] >= num) {
                index = mid;
                R = mid -1;
            } else if (arr[mid] < num) {
                L = mid + 1;
            }
        }

        return index;
    }

    //暴力破解
    public static int testLeft(int[] arr, int num) {
        int index = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= num) {
                index = i;
                return index;
            }
        }

        return index;
    }
}
